package main

import "sort"

func makesquare(matchsticks []int) bool {
    totalLen := 0
    for _, l := range matchsticks {
        totalLen += l
    }
    if totalLen%4 != 0 {  // 如果不是4的倍数，则不可能是正方形
        return false
    }
    sort.Sort(sort.Reverse(sort.IntSlice(matchsticks))) // 减少搜索量

    edges := [4]int{}
    var dfs func(int) bool
    dfs = func(idx int) bool {
        if idx == len(matchsticks) {
            return true
        }
        for i := range edges {
            edges[i] += matchsticks[idx]
            if edges[i] <= totalLen/4 && dfs(idx+1) {
                return true
            }
            edges[i] -= matchsticks[idx]
        }
        return false
    }
    return dfs(0)
}
